Supply Chain Chaos 📉
Ships are arriving in a scrambled order. We need to calculate the 混亂指標 (number of inversions) to optimize the AI traffic controller.
什麼是逆序對？
A pair of indices $(i, j)$ is an inversion if:
- $i < j$（船隻 $i$ 在船隻 $j$ 之前抵達）
- $A[i] > A[j]$（船隻 $i$ 的優先級編號較高）
Analysis 🔍
範例序列：[2, 4, 1, 3, 5]
- ❌ (2, 1)：2 出現在 1 之前，但 2 > 1
- ❌ (4, 1)：4 出現在 1 之前，但 4 > 1
- ❌ (4, 3)：4 出現在 3 之前，但 4 > 3
- 總混亂度：3 個逆序對
挑戰
A brute force nested loop is $O(N^2)$.
for i in range(n):
for j in range(i+1, n): ...
for j in range(i+1, n): ...
For $N=100,000$, this takes ~10 billion ops. 結果：超過時間限制。